#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

// 面试题 16.25. LRU 缓存
// https://leetcode.cn/problems/lru-cache-lcci/description/

class LRUCache
{
private:
    list<pair<int, int>> KVList;
    unordered_map<int, list<pair<int, int>>::iterator> recordKV;
    int listCapacity;

public:
    LRUCache(int capacity)
    :listCapacity(capacity){

    }

    int get(int key)
    {
        if(recordKV.find(key) == recordKV.end()){
            return -1;
        }
        KVList.splice(KVList.end(), KVList, recordKV[key]);
        return recordKV[key]->second;
    }

    void put(int key, int value)
    {
        if(recordKV.find(key) == recordKV.end()){
            if(recordKV.size() == listCapacity){
                int K = KVList.front().first;
                KVList.pop_front();
                recordKV.erase(K);
            }
            recordKV[key] = KVList.insert(KVList.end() ,{key, value});
            
        }else{
            KVList.splice(KVList.end(), KVList, recordKV[key]);
            recordKV[key]->second = value;
        }
    }
};

int main()
{
    return 0;
}